package com.leo.leetcode.s100;

/**
 *
 * @author xuexiaolei
 * @version 2017年11月20日
 */
public class T14LongestCommonPrefix {
    /**
     * 13 ms
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) return strs[0];
        if (strs.length == 0) return "";
        int i = 0;
        String res = "";
        boolean isBreak = false;
        while (true){
            for (int j = 0; j < strs.length-1; j++) {
                String s = strs[j];
                String sn = strs[j+1];
                if (s.length() <= i || sn.length() <=i || s.charAt(i)!=sn.charAt(i)){
                    isBreak = true;
                    break;
                }
                if (j == strs.length-2){
                    res+=s.charAt(i);
                    i++;
                }
            }
            if (isBreak) break;
        }
        return res;
    }

    /**
     * 14 ms 这不科学啊
     * @param strs
     * @return
     */
    public static String longestCommonPrefix2(String[] strs) {
        if (strs.length == 1) return strs[0];
        if (strs.length == 0) return "";
        int i = 0;
        boolean isBreak = false;
        while (true){
            for (int j = 0; j < strs.length-1; j++) {
                String s = strs[j];
                String sn = strs[j+1];
                if (s.length() <= i || sn.length() <=i || s.charAt(i)!=sn.charAt(i)){
                    isBreak = true;
                    break;
                }
                if (j == strs.length-2){
                    i++;
                }
            }
            if (isBreak) break;
        }
        return strs[0].substring(0,i);
    }

    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{}));
        System.out.println(longestCommonPrefix(new String[]{"abc"}));
        System.out.println(longestCommonPrefix(new String[]{"abc","a"}));
        System.out.println(longestCommonPrefix(new String[]{"abc",""}));
        System.out.println(longestCommonPrefix(new String[]{"abc","","a"}));
        System.out.println(longestCommonPrefix(new String[]{"abc","ab","a"}));
        System.out.println(longestCommonPrefix(new String[]{"abc","ab","ab"}));
        System.out.println(longestCommonPrefix2(new String[]{"abc","ab","ab"}));
        System.out.println(longestCommonPrefix2(new String[]{"abcd","abc","abc"}));
    }
}
